package com.haidechizi.leetcode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class _113_路径总和II {

    public List<List<Integer>> pathSum(TreeNode root, int sum) {

        List<List<Integer>> result = new ArrayList<>();
        Stack<Integer> stack = new Stack<>();
        generate(root, result, stack, sum);
        return result;

    }

    private void generate(TreeNode root, List<List<Integer>> result, Stack<Integer> stack, int sum) {
        if (root == null) {
            return;
        }
        stack.push(root.val);
        if (root.left == null && root.right == null) {
            addResult(result, stack, sum);
        }
        generate(root.left, result, stack, sum);

        generate(root.right, result, stack, sum);

        stack.pop();
    }

    private void addResult(List<List<Integer>> result, Stack<Integer> stack, int sum) {
        int count = 0;
        for (Integer value : stack) {
            count += value;
        }
        if (sum == count) {
            List<Integer> list = new ArrayList<>();
            list.addAll(stack);
            result.add(list);
        }
    }
}
